package day8;

import java.util.HashMap;
import java.util.PriorityQueue;

public class code2 {

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode bg = new ListNode();
        int num = 0;
        ListNode node = bg;
        while (l1!=null||l2!=null){
            int m = 0;
            int n = 0;
            if(l1!=null){
                m = l1.val;
                l1 = l1.next;
            }
            if(l2!=null){
                n = l2.val;
                l2 = l2.next;
            }
            node.next = new ListNode((m+n+num)%10);
            num = (m+n+num)/10;
            node = node.next;
        }
        if(num>0){
            node.next = new ListNode(num);
        }

        return bg.next;
    }

    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode fast = head;
        ListNode slow = head;

        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }
        while (fast.next!=null){
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;

        return head;

    }

    public ListNode swapPairs(ListNode head) {
        if(head==null) return null;

        ListNode node = new ListNode();

        ListNode n = node;
        ListNode a = head;
        ListNode b = head;

        while (a!=null){
            b = a.next;

            if(b==null){
                n.next = a;
                break;
            }else {
                ListNode flag = b.next;

                n.next = b;
                b.next = a;
                a.next = null;

                n = a;
                a = flag;

            }

        }

        return node.next;

    }


    public ListNode reverseKGroup(ListNode head, int k) {

        ListNode node = new ListNode();

        ListNode p = node;
        ListNode q = head;

        while (q!=null){
            ListNode f = q;
            ListNode n = q;

            for (int i = 0; i < k-1; i++) {
                if(n==null) break;
                n = n.next;
            }

            if(n==null){
                p.next=q;
                break;
            }

            for (int i = 0; i < k; i++) {
                ListNode t = q.next;
                q.next = p.next;
                p.next = q;
                q = t;
            }
            p = f;
        }

        return node.next;

    }

    public Node copyRandomList(Node head) {

        HashMap<Node,Node> map = new HashMap<>();
        map.put(null,null);
        Node l = head;
        while (l!=null){
            map.put(l,new Node(l.val));
        }
        l = head;
        while (l!=null){
            map.get(l).next = map.get(l.next);
            map.get(l).random = map.get(l.random);
        }
        return map.get(head);

    }

    public ListNode sortList(ListNode head) {
        if(head==null) return null;
        if(head.next==null) return head;
        ListNode slow = head;
        ListNode fast = head;

        while (fast.next!=null&&fast.next.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode n = slow.next;
        slow.next = null;
        ListNode t1 = sortList(head);
        ListNode t2 = sortList(n);

        return div(t1,t2);
    }


    public ListNode div(ListNode node1,ListNode node2){
        ListNode n = new ListNode();
        ListNode node = n;
        while (node1!=null&&node2!=null){
            if(node1.val<node2.val){
                ListNode p = node1.next;
                node1.next = null;
                node.next = node1;
                node = node.next;
                node1 = p;
            }else {
                ListNode p = node2.next;
                node2.next = null;
                node.next = node2;
                node = node.next;
                node2 = p;
            }
        }
        if(node1==null) node.next=node2;
        if(node2==null) node.next=node1;
        return n.next;
    }


    public ListNode mergeKLists(ListNode[] lists) {

        PriorityQueue<ListNode> queue = new PriorityQueue<>((a,b)-> a.val-b.val);

        ListNode node = new ListNode();
        ListNode n = node;

        for (int i = 0; i < lists.length; i++) {
            queue.offer(lists[i]);
        }

        while (!queue.isEmpty()){
            ListNode k = queue.poll();
            if(k.next!=null) queue.offer(k.next);
            k.next = null;
            n.next = k;
            n = k;
        }

        return node.next;

    }



}
